import gen as g
import random
import time
import alg as a 
s = a.Solution()
l = []
# 在此处编写需要测试时间的代码
for i in range(0,13,2):
    start_time = time.perf_counter()  # 开始计时
    nums1 ,nums2 , k = g.generate_data(i, i)    
    s.maxNumber(nums1, nums2, k)
    end_time = time.perf_counter()  # 结束时间
    
    time_used = end_time - start_time  # 计算程序运行时间
    l.append(time_used)

from typing import List



def test_generateParenthesis():
    s = Solution()
    start_time = time.perf_counter()  # 开始计时
    # 测试样例1，期望输出 ["((()))", "(()())", "(())()", "()(())", "()()()"]
    n1 = 3
    res1 = s.generateParenthesis(n1)
    assert len(res1) == 5
    assert set(res1) == set(["((()))", "(()())", "(())()", "()(())", "()()()"])
    end_time = time.perf_counter()  # 结束时间
    
    time_used = end_time - start_time  # 计算程序运行时间
    l.append(time_used)

    start_time = time.perf_counter()  # 开始计时
    # 测试样例2，期望输出 ["()"]
    n2 = 1
    res2 = s.generateParenthesis(n2)
    assert len(res2) == 1
    assert res2 == ["()"]
    end_time = time.perf_counter()  # 结束时间
    
    time_used = end_time - start_time  # 计算程序运行时间
    l.append(time_used)

    start_time = time.perf_counter()  # 开始计时
    # 测试样例3，期望输出 ["", "(())", "()()"]
    n3 = 2
    res3 = s.generateParenthesis(n3)
    assert len(res3) == 3
    assert set(res3) == set(["", "(())", "()()"])
    end_time = time.perf_counter()  # 结束时间
    
    time_used = end_time - start_time  # 计算程序运行时间
    l.append(time_used)

#贪心
import random
from typing import List

class Solution:
    def largestOddNumber(self, num: str) -> str:
        n = len(num)
        for i in range(n-1,-1,-1):
            if int(num[i])%2==1:
                return num[:i+1]
        return ""

# 创建 Solution 类的实例
solution = Solution()

# 随机生成测试数据
num = "".join([str(random.randint(0, 9)) for _ in range(random.randint(1, 10))])

# 打印测试数据
print("测试数据：", num)

# 调用 largestOddNumber 方法进行测试
result = solution.largestOddNumber(num)

# 输出测试结果
print("最大奇数为：", result)


#回溯
import random
from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        def dfs(node, current_sum, path):
            if not node:
                return
            current_sum += node.val
            path.append(node.val)
            if not node.left and not node.right and current_sum == targetSum:
                result.append(path[:])
            dfs(node.left, current_sum, path)
            dfs(node.right, current_sum, path)
            path.pop()

        result = []
        dfs(root, 0, [])
        return result

# 创建 Solution 类的实例
solution = Solution()

# 随机生成二叉树
def generate_tree() -> TreeNode:
    if random.random() < 0.5:
        return None
    val = random.randint(-100, 100)
    left = generate_tree()
    right = generate_tree()
    return TreeNode(val, left, right)

root = generate_tree()

# 随机生成目标和
target_sum = random.randint(-1000, 1000)

# 打印测试数据和调用方法：

print("二叉树：", root)
print("目标和：", target_sum)

# 调用 pathSum 方法进行测试
result = solution.pathSum(root, target_sum)

# 输出测试结果
print("结果：", result)



#动态规划
import random
from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

# 创建 Solution 类的实例
solution = Solution()

# 随机生成测试数据
m, n = random.randint(1, 10), random.randint(1, 10)  # 随机生成网格的行数和列数
grid = [[random.randint(1, 10) for _ in range(n)] for _ in range(m)]  # 随机生成网格

# 打印测试数据
print("测试数据：")
for row in grid:
    print(row)

# 调用 minPathSum 方法进行测试
result = solution.minPathSum(grid)

# 输出测试结果
print("最小路径数字总和为：", result)

#贪心算法：[135. 分发糖果]
import random
from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candyVec = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candyVec[i] = candyVec[i - 1] + 1
        for j in range(len(ratings) - 2, -1, -1):
            if ratings[j] > ratings[j + 1]:
                candyVec[j] = max(candyVec[j], candyVec[j + 1] + 1)
        return sum(candyVec)

if __name__ == '__main__':
    # 生成随机测试数据
    ratings = [random.randint(1, 100) for _ in range(10)]
    # 创建解决方案对象
    solution = Solution()
    # 调用 candy 方法
    result = solution.candy(ratings)
    # 输出结果
    print("Ratings: ", ratings)
    print("Minimum number of candies: ", result)


#回溯算法：[51. N 皇后]
import random
from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if not n: return []
        board = [['.'] * n for _ in range(n)]
        res = []
        def isVaild(board, row, col):
            #判断同一列是否冲突
            for i in range(len(board)):
                if board[i][col] == 'Q':
                    return False
            # 判断左上角是否冲突
            i = row -1
            j = col -1
            while i>=0 and j>=0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            # 判断右上角是否冲突
            i = row - 1
            j = col + 1
            while i>=0 and j < len(board):
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1            
                return True

        def backtracking(board, row, n):
            # 如果走到最后一行，说明已经找到一个解
            if row == n:
                temp_res = []
                for temp in board:
                    temp_str = "".join(temp)
                    temp_res.append(temp_str)
                res.append(temp_res)
            for col in range(n):
                if not isVaild(board, row, col):
                    continue
                board[row][col] = 'Q'
                backtracking(board, row+1, n)
                board[row][col] = '.'
        backtracking(board, 0, n)
        return res

if __name__ == '__main__':
    # 生成随机测试数据
    n = random.randint(1, 10)
    # 创建解决方案对象
    solution = Solution()
    # 调用 solveNQueens 方法
    result = solution.solveNQueens(n)
    # 输出结果
    print("N: ", n)
    print("Solutions: ", result)

#贪心算法：[406.根据身高重建队列]

import random
from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        que = []

        for p in people:
            que.insert(p[1], p)
        return que

if __name__ == '__main__':
    # 生成随机测试数据
    n = random.randint(1, 10)
    people = [[random.randint(1, 100), random.randint(0, n-1)] for _ in range(n)]
    # 创建解决方案对象
    solution = Solution()
    # 调用 reconstructQueue 方法
    result = solution.reconstructQueue(people)
    # 输出结果
    print("People: ", people)
    print("Reconstructed queue: ", result)

import generator
import alg
import time
import numpy as np
import random
import string
import numpy as np
import matplotlib.pyplot as plt
def runtime(func,data):
    start=time.perf_counter()
    func(data)
    end=time.perf_counter()
    return end-start
obj=alg.Solution()
x=generator.data()
y1=np.array([runtime(obj.maxArea,x[0]),runtime(obj.maxArea,x[1]),runtime(obj.maxArea,x[2]),runtime(obj.maxArea,x[3])])
plt.plot([100,500,900,1300],y1,label="成水最多的容器")

y2=np.array([runtime(obj.maxSubArray,x[0]),runtime(obj.maxSubArray,x[1]),runtime(obj.maxSubArray,x[2]),runtime(obj.maxSubArray,x[3])])
plt.plot([100,500,900,1300],y2,label="最大子序列和")
plt.legend(loc='upper right')
plt.rcParams['font.sans-serif']=['SimHei']


plt.figure()
y3=np.array([runtime(obj.permute,[1]),runtime(obj.permute,[1,2]),runtime(obj.permute,[1,2,3]),runtime(obj.permute,[1,2,3,4])])
plt.plot([1,2,3,4],y3,label="全排列")
plt.legend(loc='upper right')
plt.rcParams['font.sans-serif']=['SimHei']
plt.show()








